import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-01-26
 * Time: 22:51
 */
public class test1 {
    /**
     * LeetCode 76 最小覆盖子串
     */

    public String minWindow(String s, String t) {
        // 特殊情况
        if (t.length() > s.length()) {
            return "";
        }
        // key是字符串的字符，value是出现的次数（int）
        Map<Character, Integer> hash = new HashMap<>();
        // 记录位置
        int ansL = -1;
        int ansR = -1;
        // 将t的字符放入哈希表中
        for (int i = 0; i < t.length(); i++) {
            hash.put(t.charAt(i), hash.getOrDefault(t.charAt(i), 0) + 1);
        }
        int size = hash.size();
        // 滑动窗口
        int right = 0;
        int left = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            // 进窗口
            if (hash.containsKey(c)) {
                hash.put(c, hash.get(c) - 1);
                if (hash.get(c) == 0) {
                    // 利用size统计还剩几个有效字符
                    size--;
                }
            }
            right++;
            // 所有有效字符都出现了的情况
            while (size == 0) {
                // 统计结果
                if (ansL == -1 || right - left < ansR - ansL) {
                    ansL = left;
                    ansR = right;
                }
                char c1 = s.charAt(left);
                if (hash.containsKey(c1)) {
                    hash.put(c1, hash.get(c1) + 1);
                    if (hash.get(c1) == 1) {
                        // 重新更新left的有效字符
                        size++;
                    }
                }
                left++;
            }
        }
        return ansL==-1?"":s.substring(ansL, ansR);
    }
}
